// 6.53 试编写算法，求给定二叉树上从根结点到叶子结点的一条其路径长度等于树的深度减一的路径（即列出从根结点到该叶子结点的结点序列），若这样的路径存在多条，则输出路径终点（叶子结点）在“最左”的一条。

#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"

void fun_6_53(tree *root, int k)
{
    tree *stack[100];
    int top = -1;
    stack[++top] = root;
    int flag[100] = {0};
    while (top >= 0)
    {
        tree *p = stack[top];
        if (top == k - 1)
        {
            for (int i = 0; i <= top; i++)
            {
                printf("%3d", stack[i]->data);
            }
            break;
        }
        switch (flag[top])
        {
        case 0:
            flag[top]++;
            if (p->left)
            {
                stack[++top] = p->left;
            }
            break;
        case 1:
            flag[top]++;
            if (p->right)
            {
                stack[++top] = p->right;
            }
            break;
        case 2:
            flag[top] = 0;
            top--;
            break;
        default:
            break;
        }
    }
}

int main()
{
    /*******************code*******************/
    int n = 15;
    int a1[15] = {1,
                  2, 3,
                  NULL, 5, NULL, NULL,
                  NULL, NULL, 7, 8, NULL, NULL, NULL, NULL};
    tree *root;
    CreatTree(root, a1, n, 0);
    fun_6_53(root, 4);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
